class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        # 最多分为4段
        SEG_COUNT = 4  # 定义IP地址的段数
        ans = list()  # 定义答案列表
        segments = [0] * SEG_COUNT  # 定义IP地址的每一段（这里是用数字表示）

        def dfs(segId: int, segStart: int):
            # 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
            if segId == SEG_COUNT:
                if segStart == len(s):
                    # 组合答案
                    ipAddr = ".".join(str(seg) for seg in segments)
                    ans.append(ipAddr)
                # 回溯寻找其他答案
                return

            # 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯，当前答案组合不满足，找其他的
            if segStart == len(s):
                return

            # 设置拦截条件，segStart是当前字符串游标，segId是IP第几段的游标
            # 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
            if s[segStart] == "0":
                segments[segId] = 0
                # 递归去下一段里面找
                dfs(segId + 1, segStart + 1)
                return

            # 一般情况，枚举每一种可能性并递归
            addr = 0

            # 遍历字符串
            for segEnd in range(segStart, len(s)):
                # 这里是将字符串转换成数字，并判断是否在0-255之间，实际上int也能，*10是为了让数字左移动，而不是直接的相加
                addr = addr * 10 + (ord(s[segEnd]) - ord("0"))
                # 是否0~255
                if 0 < addr <= 0xFF:
                    # 当前段先放着，表示找到一种答案，然后继续递归
                    segments[segId] = addr
                    dfs(segId + 1, segEnd + 1)
                else:
                    break

        dfs(0, 0)
        return ans
